1. Field of the Invention
This invention relates to switching circuitry and, more particularly, to an m-to-n concentrator constructed from smaller concentrator/sorters or sorters.
2. Description of the Background Art
A switch with an array of m input ports and an array of n output ports is said to be a switch of “size” m×n. One convention linearly labels the m input ports and the n output ports with, respectively, m and n distinct addresses. Usually, the addresses start from 0, so that the m input ports and n output ports are linearly labeled as 0, 1, . . . , m−1 and 0, 1, . . . , n−1, respectively (in a top-down manner if one visualizes a graphical representation of the input and output ports of the switch in a planar view). This inventive subject matter pertains to m×m switches and, particularly, to a special type of switch designated a “concentrator”.
An m×m “sorter” is an m×m switch that compares the values of the m input signals and routes the m input signals to the m output ports such that the values of the m signals are monotonically increasing with respect to the output addresses. A number of signals are said to be monotonically increasing with respect to the output addresses if the value of the signal routed to any particular output address is always not less than that of any other signal routed to a smaller output address. Similarly, a number of signals are said to be monotonically decreasing with respect to the output addresses if the value of the signal routed to any particular output address is always not less than that of any other signal routed to a larger output address. Here an input signal may possibly be an idle expression that is artificially generated at an input port when there is no real data input signal arriving at that input port. As per the graph representation, since the m output ports of an m×m switch are by default labeled from 0 to m−1 in the top-down manner, for a default m×m sorter, any signal routed to a lower output port cannot be less than those routed to upper output ports. Thus signal values on the output side are linearly sorted. For example, FIG. 1 shows a 6×6 sorter 100 as described above. The six input signals 101 assume different integer values and are linearly sorted on the output side 102 of the sorter according to their values.
In a wider sense, an m×m sorter can still be regarded as an m×m sorter even if the ordering of output ports is rotated, flipped, and/or even otherwise permuted in a predetermined fashion, as long as it observes the principle qualification of a sorter that the value of the signal routed to any particular output address is not less than that of any other signals routed to smaller output addresses. For example, FIG. 2 shows a 6×6 wide-sense sorter 200 which sorts the six input signals 201 into a rotation of an increasing sequence 202. For simplicity, and without loss of generality, the sorters appearing in the sequel are of the default type as the one shown in FIG. 1 unless otherwise specified.
A 2×2 sorter is conventionally called a “sorting cell”. A default sorting cell always routes the larger one of its two local input signals to its lower output port. All sorting cells appearing hereafter are of the default version unless otherwise specified.
For n<m, an “m-to-n concentrator” is an m×m switch that routes the largest n among the m input signals to the n output ports with the n largest output addresses and the smallest m−n among the m input signals to the m−n output ports with the m−n smallest output addresses. Thus the m output ports can be thought of being partitioned into a “1-output group” and a “0-output group”, with the former comprising the n output ports with the n largest addresses and the latter comprising the remaining m−n output ports. Then, an m-to-n concentrator can be regarded as a device which is capable of partitioning the m input signals (including real data input signals and artificial idle expressions) into two groups: the group of n largest signals, which are routed to the 1-output group, and the group of m−n smallest signals, which are routed to the 0-output group. As per the graph representation, by default the m-to-n concentrator is the one wherein the upper m−n output ports form the 0-output group and the lower n output ports form the 1-output group. FIG. 3A shows a 6-to-2 concentrator 300. The two signals of largest values 303 are routed to the 1-output group 301, the group of the lower two output ports, wherein the order between these two signals is arbitrary. Meanwhile, the four signals of smaller values 304 are routed to the 0-output group 302, the group of the upper four output ports, within which the order among the signals is also arbitrary. Similar to the case of sorters, the definition of an m-to-n concentrator in a wider sense allows the rotation, flipping, and/or any other permutations, of the ordering of output ports. Anyway, for any m-to-n concentrator, the 0-output group always comprises the m−n output ports with the smallest m−n output addresses while the 1-output group comprises the n output ports with the largest n output addresses. The only difference between the default and the wide-sense versions lies on the labeling of the m output addresses. For a default m-to-n concentrator, the m output ports are labeled from 0 to m−1 from top to bottom such that the 0-output group always comprises the upper m−n output ports and the 1-output group the lower n output ports. On the other hand, for a wide-sense m-to-n concentrator, the labeling of the m output ports, which is also from 0 to m−1, can be in any predetermined fashion, so the 0-output group can comprise any m−n distinct output ports and the 1-output group the remaining n output ports. FIG. 4 shows an example of a 6-to-2 concentrator 400 in such a wide sense wherein the six output ports are labeled as 0, 1, . . . , 5 from bottom to top such that the two signals of largest values 403 are routed to the 1-output group 401, which is now comprising the upper two output ports.
In some references in the background art, there is notion of an “m×n concentrator”, which means an m×n switch, n<m, such that the largest n input signals are routed the n output ports. Thus an m-to-n concentrator can be reduced to an “m×n concentrator” by not implementing output ports in the 0-output group. FIG. 3B shows a 6×2 concentrator 310 by which only the two largest signals are routed to the two output ports 311. As stated above, this 6×2 concentrator may result from the 6-to-2 concentrator 300 in FIG. 3A with the upper four output ports 302 not implemented.
In order to avoid terminology ambiguity, the notion of an “m×n concentrator” will not be adopted. Every concentrator in this context refers to an m-to-n concentrator for some m and some n, n<m.
For any n<m, by letting the lower n outputs of an m×m sorter form the 1-output group and the upper m−n outputs form the 0-output group, the m×m sorter automatically qualifies as an m-to-n concentrator. One way to view the difference between an m×m sorter and a generic m-to-n concentrator is that the former provides a linear ranking among the n signals in the 1-output group and also a linear ranking among the m−n signals in the 0-output group.
For n≦m, an “m-to-n concentrator/sorter” is an m×m switch that routes the smallest m−n among input signals to the m−n smallest output addresses, which form the 0-output group, and the largest n among input signals to the n largest output addresses, which form the 1-output group, such that the values of these n signals are nondecreasing with respect to output addresses. In other words, an m-to-n concentrator/sorter not only is an m-to-n concentrator but also routes signals in a way such that the n signals reaching the 1-output group are sorted; the m−n signals reaching the 0-output group, however, are not necessarily sorted. FIG. 5 shows a (default) 6-to-3 concentrator/sorter 500 as an example wherein the three signals 501 of largest values are grouped together at the bottom and are also linearly sorted while the remaining smaller ones 502 are grouped at the top without sorting. Like the sorter and the concentrator, the concentrator/sorter also has the wide-sense version, but the concentrator/sorters appeared in the context are of the default version unless otherwise specified.
For any n≦m, by letting the lower n outputs of an m×m sorter form the 1-output group and the upper m−n outputs form the 0-output group, the m×m sorter automatically qualifies as an m-to-n concentrator/sorter. Thus an m×m sorter is a special case of an m-to-n concentrator/sorter for all n≦m.
Note that the comparison performed in a sorter, a concentrator, or a concentrator/sorter is based on the order defined over all of the possible values of an input signal, thus a sorter, a concentrator, or a concentrator/sorter should always be associated with an order. This order may vary from application to application and can even be any artificial one. For example, in certain applications of packet switching, the legitimate values of an input signal to a concentrator are “00”, “10”, and “11”, and the concentrator is associated with an artificial order “10”<“00”<“11” which looks awkward but is practically very useful.
An m-to-n concentrator associated with a particular order among all possible values of an input signal automatically becomes an m-to-(m−n) concentrator associated with the reverse of that order if the output ports of the m-to-n concentrator are re-labeled such that the n output ports in the 1-output group of the m-to-n concentrator, that is, the n output ports with the n largest addresses, are now labeled with the n smallest addresses and thus form the new 0-output group of the m-to-(m−n) concentrator, and similarly the 0-output group of the m-to-n concentrator now becomes the new 1-output group of the m-to-(m−n) concentrator. For example, consider FIG. 3A again. The 6-to-2 concentrator 300 associated with the natural order is equivalent to a 6-to-4 concentrator associated with the reversed natural order, that is, “0”>“1”>“2”> . . . , when the output addresses are re-labeled in the reversed order. The same argument applies to the m-to-n concentrator/sorter.
In background art references, sorters, concentrators, concentrator/sorters, and other switching devices with sorting capabilities are collectively referred to as sorting devices. They can be constructed by various types of architectures, such as crossbar, shared-buffer memory, and multi-stage interconnection network of sorting cells. A multi-stage interconnection network means a collection of interconnected nodes, where the nodes are grouped into a number of stages such that every interconnection line is between two nodes on adjacent stages. Some architectures involve centralized control, which requires high processing and memory speeds and hence is suitable for implementing devices with small number of I/Os but inevitably imposes a bottleneck on the performance when the number of I/Os becomes large. Architectures in the type of multi-stage interconnection network of sorting cells can avoid the centralized control as follows. Every data unit includes an “in-band control signal” followed by a payload. When two data units respectively enter the two input ports of a sorting cell in the multi-stage interconnection network, the “in-band control signals” of the two data units are used as the “input signals to the sorting cell” for comparison. Note that this means the switching decision of the sorting cell is purely determined by just the two “in-band control signals” of two data units and is independent of all other concurrent data units in the multi-stage interconnection network regardless the scale of the network. In this sense, the in-band control of a multi-stage network of sorting cells is extremely distributed.
When a data unit is routed through a multi-stage interconnection network, it may traverse a sorting cell on every stage of the network and its “in-band control signal” is preserved throughout. Since the switching control at all sorting cells on its route is by the simple comparison of the value of its “in-band control signal” against another value, it appears as if the routing of each individual signal through the network is guided by the value of the signal itself. This distributed control mechanism is sometimes referred to as “self-routing” in the literature. Self-routing control over a multi-stage interconnection network of sorting cells enables the construction of large-scale switching devices.
There exist many ways to construct an m-to-n concentrator/sorter. Algorithms for the construction of an m-to-n concentrator/sorter by multi-stage interconnection of sorting cells include, as representative of the art, the so-called “knockout tournaments” technique as disclosed by Y. S. Yeh, M. G. Hluchyj, and A. S. Acampora, “The Knockout Switch: A Simple Modular Architecture for High Performance Packet Switching,” IEEE J. Select. Areas Commun., vol. 5, pp. 1274–1283, 1987.
In a reference entitled “Concentrators in ATM switching,” Comp. Sys. Sci. Eng., vol. 6, pp. 335–342, 1996, authored in S. -Y. R. Li and C. -M. Lau (Li-Lau), the authors devised and discussed a special m-to-n concentrator, where m=2n, as constructed from two n×n sorters and n sorting cells.
There are no teachings or suggestions of, and thus the art is devoid of, how to generalize the subject matter of the references, and especially of Li-Lau, to handle the construction of an m-to-n concentrator from two concentrator/sorters or sorters and n sorting cells where m is not necessarily equal to 2n.